/*
Date:20210502 18:03PM
key:经典动态规划。定义dp[i]是考虑i及以前的最大收获。由两种子状态，加当前与不加当前转换而来。
*/
class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int*dp=new int[nums.size()];
        if(nums.size()==1){return nums[0];}
        if(nums.size()==2){return max(nums[0],nums[1]);}
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++)
        {

            
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
            
            
        }
        return dp[nums.size()-1];
    }
};